\chapter{Анализ производетельности трассировки лучей в воксельном октарном дереве}

В данном разделе представленны некоторые наблюдения влияния различных аспектов реализации и параметров трассировщика на производительность трассировки лучей в октарном дереве, реализованном при помощи технологии CUDA. Отметим, что производительность достаточно сильно зависит от сложности геометрии, поподающей в поле зрения наблюдателя, поэтому все замеры производительности производились при визуализации одного и того же участка сцены, который изображен на рис.~\ref{fig:trace_scene}.

\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{trace.jpg}
\caption{Тестовая сцена}
\label{fig:trace_scene}
\end{figure}

Основное внимание в этом разделе уделяется вопросам балансировки вычислительной нагрузки и эффективной работе с памятью GPU.

\section{Балансировка вычислительной нагрузки}

Заметим, что количество итераций алгоритма трассировки на пиксель может сильно различатся для лучей, порожденных разными пикселями. На рис.~\ref{fig:trace_iters} показано количество итераций аглоритма трассировки, требуемое для каждого пикселя изображения. Среднее количество итераций близко к 50, однако, для отдельных пикселей изображения может достигать нескольких сотен. На рис.~\ref{fig:trace_iter_distrib} показано распределение количества итераций на луч.

На каждой итерации осуществляется одно из следующих действий:

\begin{itemize}
  \item Спуск вниз по октарному дереву на один уровень.
  \item Переход к следующему пересекаемому лучем узлу дерева, с возможным подьемом на несколько уровней.
  \item Сохранение результата при пересечении луча с непустым вокселем.
\end{itemize}

\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{trace_iters.jpg}
\caption{Количество итераций алогритма трассировки на пиксель}
\label{fig:trace_iters}
\end{figure}

\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{ballance/trace_iter_distrib.pdf}
\caption{Распределение количества итераций на луч}
\label{fig:trace_iter_distrib}
\end{figure}

В большинстве областей изображения количество итераций на пиксель достаточно однородно, однако, в местах, где лучи проходят по касательной к поверхности, возникают разрывы во времени работы алгоритма для соседних пикселей. Так, группы соседних пикселей трассируются потоками, лежащими в однов warp'е, это может првести в простою потоков, завершивших трассировку, в ожидание из более медленных соседей. Механизм возникновения этого явления показан на рис.~\ref{fig:warp_loads}.

\begin{figure}[h]
\center
\includegraphics[width=.8\textwidth]{ballance/warp_loads.pdf}
\caption{Различные варианты заполнения warp'ов при визуализации тестовой сцены}
\label{fig:warp_loads}
\end{figure}

В случае когеррентных потоков, среднее заполнение warp'ов составило около 81\%. Был проведен эксперимент с некогеррентными лучами. В данном эксперименте была выполнена визуализация тестовой сцены, однако задания для потоков вычисления были перемешаны таким образом, что каждый warp состоял из потоков, обрабатывавщих пиксели лежавшие в произвольных случайных частях изображения. В этом случает оффективность заполнения warp'ов снижалась до 47\%, а производительность падала более чем в два раза. Данные о производтельности трассировщика лучей при отрисовке тестовой сцены в разрешении 1024х768 представлены в таблице \ref{tab:coher_perf}.

\begin{table}[ht]
\center
\label{tab:coher_perf}
\begin{tabular}{l|p{.2\textwidth}|p{.2\textwidth}|p{.2\textwidth}}
 Лучи  & Загруженность warp'ов & Время трассировки GeForce 8800 GTS (мс) &  Время трассировки GeForce GTX 275 (мс) \\
\cline{1-4}
  Когерентные  & 81\% & 71 & 35 \\
  Некогерентные & 47\% & 143 &  72 \\
\end{tabular}
\caption{Сравнение производительности трассировщика лучей в случае когерентных и некогерентных лучей}
\end{table}

\section{Особенности работы с памятью и их влияние на производительность}

Помимо дизбаланса warp'ов на производтельность трассировщика так же влияет количество активных потоков, обрабатываемых мультипроцессорами с каждый момент времени. Для достидения максимальной производительности рекоммендуется делать это количство в несколько раз большим, чем реальное количество вычислительных устройств в мультипроцессоре. Это позволяет скрывать латентность доступа к глобальной памяти GPU засчет выполнения арифметических операций других потоков во время обжидания данных из памяти (рис.~\ref{fig:occup_pipeline}).

\begin{figure}[h]
\center
\includegraphics[width=.8\textwidth]{ballance/occup_pipeline.PNG}
\caption{Сокрытие латентности работы с глобальной памятью}
\label{fig:occup_pipeline}
\end{figure}

Путем исскуственного ограничения загруженности мультипроцессоров удалось выяснить, что с увеличением колическтва активных потоков производительность растет почти линейно в случает трассировщика лучей (рис.~\ref{fig:occup_fps}). Это говорит о том, что большую часть времени все потоки проводят в ожидании данных из пямяти.

\begin{figure}[h]
\center
\includegraphics[width=.8\textwidth]{ballance/occup_fps.PNG}
\caption{Зависимость производительности трассировщика (кадров в секунду) от количества активных warp'ов на мультипроцессор}
\label{fig:occup_fps}
\end{figure}

Для оценки действительной загруженности мультипроцессоров работой были проведены измерения, которые показали (рис.~\ref{fig:occup_time}), что на начальном этапе работы GPU распределяет задания по мультипроцессорам достаточно эффективно, а затем, когда часть warp'ов завершает свою работу, наблюдаются неожиранные колебания загрузки.

\begin{figure}[h]
\center
\includegraphics[width=.8\textwidth]{ballance/occup_time.png}
\caption{График изменения реального количества активных warp'ов на мультироцессор}
\label{fig:occup_time}
\end{figure}

На рис.~\cite{fig:occup} показано распределение згруженностей мультипроцессоров по моментам времени. В случае когерентных лучей, когда время жизни разных warp'ов может быть сильно неоднородным, средняя загруженность близка к $4.5$. В случае некогерентных потоков, когда время жизни warp'ов более предсказуемо, поланировщик заданий GPU обеспецивает несколько более высокую загруженость мультироцессоров, близкую к $6.7$, что все равно достаточно далеко от максимально возможных для данного вычислительного ядра 8 warp'ов. Стоит отметить, что вслучае некогерентных потоков, несмотря на более высокую утилизацию мультипроцессоров, производительность все равно оказывается примерно в два раза ниже, чем в случае когерентных, так как положительный эффект улучшения работы планировщика нивелируется худшим заполнением warp'ов и менее эффективной работой текстурных кэшей.

\begin{figure}[h]
\center
\includegraphics[width=.8\textwidth]{ballance/occup.png}
\caption{Распределение загруженностей мультипроцессоров для когерентного (coherent) и некогерентного (shuffled) случаев}
\label{fig:occup}
\end{figure}


\begin{figure}[h]
\center
\includegraphics[width=.8\textwidth]{trace_res_time.pdf}
\caption{Зависимость времени трассировки от разрешения}
\label{fig:trace_res_time}
\end{figure}

\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{trace_lod_time.pdf}
\caption{Зависимость времени трассировки глубины дерева}
\label{fig:trace_lod_time}
\end{figure}

\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{trace_scheduler.pdf}
\caption{Диаграмма исполнения для когерентных и перемешанных потоков}
\label{fig:trace_scheduler}
\end{figure}
